package com.itzmn.newcode.offer1;

import java.util.ArrayList;

/**
 * @Author: 张梦楠
 * @Date: 2018/12/20 16:24
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description: 二叉树中和为某一值的路径
 *
 *   输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径
 *   。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
 *   (注意: 在返回值的list中，数组长度大的数组靠前)
 *
 *   思路：深度遍历，得到值
 */
public class _24_TheBinaryTreeNeutralizesThePathToCertainValue extends Tree{

    public static void main(String[] args) {

        new _24_TheBinaryTreeNeutralizesThePathToCertainValue().test();
    }

    private void test() {
        TreeNode binaryTree = createBinaryTree(new int[]{1, 2, 3, 8, 7, 6, 5});
        ArrayList<ArrayList<Integer>> arrayLists = FindPath(binaryTree, 10);
    }

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {

        ArrayList<Integer> integers = new ArrayList<>();
        ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
        if (root == null){
            return arrayLists;
        }
        find(target,integers,root,arrayLists);
        System.out.println(arrayLists);

        return arrayLists;
    }

    private void find(int target,ArrayList<Integer> list,TreeNode root,ArrayList<ArrayList<Integer>> lists){

        list.add(root.val);
        if (target == root.val && root.left== null && root.right == null){
            lists.add(list);
        }
        ArrayList<Integer> integers = new ArrayList<>(list);
        if (root.left != null){
            find(target-root.val,list,root.left,lists);
        }
        if (root.right != null){
            find(target-root.val,integers,root.right,lists);
        }
    }
}
